package permute_combine

import (
	C "gitee.com/ljfirst/algo-go-sdk/common/constant"
	"gitee.com/ljfirst/algo-go-sdk/tools"
)

/**
 * @author ljfirst
 * @version V1.0
 * @date 2023/7/7 23:28
 * @author-Email ljfirst@mail.ustc.edu.cn
 * @blogURL https://blog.csdn.net/ljfirst
 * @description 给定不含有重复元素的数组[1,2,3],求所有的排列
 * [1,2,3]、[1,3,2]、[2,1,3]、[2,3,1]、[3,1,2]、[3,2,1]
 * */
type PermutationByChange struct {
	array []int
	ans   [][]interface{}
}

func (m *PermutationByChange) PermuteMethod(arrayI interface{}) [][]interface{} {
	array, err := tools.Interface2IntArray(arrayI)
	if err != nil {
		return nil
	}
	m.ans = make([][]interface{}, 0)
	m.array = array
	m.roll(0)
	return m.ans
}

func (m *PermutationByChange) roll(depth int) {
	if depth == len(m.array) {
		temp, _ := tools.IntArray2InterfaceArray(m.array)
		m.ans = append(m.ans, temp)
		return
	}
	// depth 代表深度，j 表示横向可以交换的数据，depth 之前的元素已经有序，只对后续元素进行全排列
	for j := depth; j < len(m.array); j++ {
		m.array[depth], m.array[j] = m.array[j], m.array[depth]
		m.roll(depth + 1)
		m.array[depth], m.array[j] = m.array[j], m.array[depth]
	}
	return
}

func (m *PermutationByChange) Tags() []string {
	return []string{C.BackTrack, C.Permutation}
}
